package cn.cnsuh.剑指offer.q59_滑动窗口的最大值;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0||k==0) return new int[0];
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for(int j = 0,i = 1 - k;j<nums.length;i++,j++){
            if(i > 0 && deque.peekFirst()==nums[i-1]){
                deque.removeFirst();//删除deque中对应的nums[i-1];
            }
            while(!deque.isEmpty()&&deque.peekLast()<nums[j]){
                deque.removeLast();//保持deque递减
            }
            deque.addLast(nums[j]);
            if(i >= 0){
                res[i] = deque.peekFirst();
            }
        }
        return res;
    }

}
